The present invention relates to data networking and more particularly to path computation in certain types of situation.
MPLS (Multi-Protocol Label Switching) Traffic Engineering has been developed to meet data networking requirements such as guaranteed available bandwidth. MPLS Traffic Engineering exploits modem label switching techniques to build guaranteed bandwidth end-to-end tunnels through an IP/MPLS network of labels switched routers (LSRs). These tunnels are a type of label switched path (LSP) and thus are generally referred to as MPLS Traffic Engineering LSPs.
Establishment of an MPLS Traffic Engineering LSP from an LSP head-end to an LSP tail-end involves computation of a path through the network of LSRs. Optimally, the computed path is the “shortest” path, as measured in some metric, that satisfies all of the relevant constraints such as e.g., required bandwidth, availability of backup bypass tunnels for each link and node included in the path, etc. Path computation can either be performed by the head-end LSR or by some other entity operating as a path computation element (PCE). The head-end (or PCE) exploits its knowledge of network topology and resources available on each link to perform the path computation according to the LSP Traffic Engineering constraints. Various path computation methodologies are available including CSPF (constrained shortest path first).
Up until now, MPLS Traffic Engineering LSPs have been configured within a single Autonomous System (AS) or Interior Gateway Protocol (IGP) area. The term “Autonomous System” generally refers to a group of routers within a network that are subject to a common authority and use the same intradomain routing protocol. It is now desirable to extend MPLS Traffic Engineering LSPs across AS boundaries. This would greatly improve traffic management and quality of service across multiple service providers over what has been achieved using prior art Border Gateway Protocol (BGP)-based techniques.
One difficulty that arises in achieving this goal is that path computation at the LSP head-end requires knowledge of network topology and resources across the entire network between the head-end and the tail-end. Yet service providers typically do not share this information with each other across AS borders. Neither the head-end nor any PCS will have sufficient knowledge to compute a path. Prior art MPLS Traffic Engineering path computation methodologies thus do not operate in an inter-AS context.
A similar problem arises in computing the paths of MPLS Traffic Engineering LSPs across what are referred to as “areas.” An area is a collection of routers that share full network topology information with each other. To improve routing scalability, a service provider may divide an AS into multiple areas. Network topology and resource information do not, however, flow across area boundaries even though a single service provider may operate all the IGP areas. Like in the inter-AS case, the standard MPLS Traffic Engineering path computation techniques cannot compute inter-area paths because overall network topology and resource information may not be available at any one node.
What is needed are systems and methods for computing the paths of MPLS Traffic Engineering LSPs across area and/or AS boundaries.